|
In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by A. Hobbs.〔〔 As colorfully write, "A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed."〔.〕 ==Equivalent characterizations== The following characterizations all describe the caterpillar trees: *They are the trees for which removing the leaves and incident edges produces a path graph.〔〔 *They are the trees in which there exists a path that contains every node of degree two or more. *They are the trees in which every node of degree at least three has at most two non-leaf neighbors. *They are the trees that do not contain as a subgraph the graph formed by replacing every edge in the star graph ''K''1,3 by a path of length two.〔 *They are the connected graphs that can be drawn with their vertices on two parallel lines, with edges represented as non-crossing line segments that have one endpoint on each line.〔〔.〕 *They are the trees whose square is a Hamiltonian graph. That is, in a caterpillar, there exists a cyclic sequence of all the vertices in which each adjacent pair of vertices in the sequence is at distance one or two from each other, and trees that are not caterpillars do not have such a sequence. A cycle of this type may be obtained by drawing the caterpillar on two parallel lines and concatenating the sequence of vertices on one line with the reverse of the sequence on the other line.〔.〕 *They are the trees whose line graphs contain a Hamiltonian path; such a path may be obtained by the ordering of the edges in a two-line drawing of the tree. More generally the number of edges that need to be added to the line graph of an arbitrary tree so that it contains a Hamiltonian path (the size of its Hamiltonian completion) equals the minimum number of edge-disjoint caterpillars that the edges of the tree can be decomposed into.〔.〕 *They are the connected graphs of pathwidth one.〔 *They are the connected triangle-free interval graphs.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「caterpillar tree」の詳細全文を読む スポンサード リンク
|